from collections import defaultdict
from typing import List


class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        def find(nums, t):
            hash_words = defaultdict(int)
            i = 0
            cnt = 0
            for j in range(len(nums)):
                hash_words[nums[j]] += 1
                while len(hash_words) > t:
                    hash_words[nums[i]] -= 1
                    if hash_words[nums[i]] == 0:
                        del hash_words[nums[i]]
                    i += 1
                cnt += j - i + 1
            return cnt

        return find(nums, k) - find(nums, k - 1)


if __name__ == '__main__':
    s = Solution()
    r = s.subarraysWithKDistinct(nums=[1, 2, 1, 2, 3], k=2)
    print(r)
